package me.wangshier.leetcode.medium;

import java.util.Stack;

/**
 * 16. 最大矩形面积问题
 *
 * @Author: tongqianwen
 * @Date: 2025/3/7
 */
public class MaximumRectangleArea {

    public static int solution(int n, int[] array) {
        int maxArea = 0;
        // 创建一个单调栈
        Stack<Integer> stack = new Stack<>();

        // 遍历数组
        for (int i = 0; i <= array.length; i++) {
            // 当前高度，如果 i 等于数组长度，高度为 0，用于处理栈中剩余元素
            int currentHeight = (i == array.length) ? 0 : array[i];

            // 如果栈不为空且当前高度小于栈顶元素对应的高度
            while (!stack.isEmpty() && currentHeight < array[stack.peek()]) {
                // 弹出栈顶元素
                int height = array[stack.pop()];
                // 计算宽度
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                // 计算面积并更新最大面积
                maxArea = Math.max(maxArea, height * width);
            }

            // 将当前索引入栈
            stack.push(i);
        }

        return maxArea;
    }


    public static int solution1(int n, int[] array) {
        int maxArea = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = i; j < array.length; j++) {

                int minimumHeight = findMin(array, i, j);
                int area = minimumHeight * (j - i + 1);
                if (maxArea < area) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }

    static int findMin(int[] array, int i, int j) {
        int min = array[i];
        for (int k = i; k <= j; k++) {
            if (array[k] < min) {
                min = array[k];
            }
        }
        return min;
    }

    public static void main(String[] args) {
        // Add your test cases here

        System.out.println(solution(8, new int[]{1, 5, 4, 2, 3, 4, 3, 3}) == 14);
        System.out.println(solution(5, new int[]{5, 4, 2, 3, 4}) == 10);
        System.out.println(solution(6, new int[]{5, 4, 3, 2, 1, 6}) == 9);
        System.out.println(solution(5, new int[]{1, 2, 3, 4, 5}) == 9);
    }
}
